{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #下载插件"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #math #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数学 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: leastMinutes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #下载插件"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "小扣打算给自己的 **VS code** 安装使用插件，初始状态下带宽每分钟可以完成 `1` 个插件的下载。假定每分钟选择以下两种策略之一:\r\n",
    "- 使用当前带宽下载插件\r\n",
    "- 将带宽加倍（下载插件数量随之加倍）\r\n",
    "\r\n",
    "请返回小扣完成下载 `n` 个插件最少需要多少分钟。\r\n",
    "\r\n",
    "注意：实际的下载的插件数量可以超过 `n` 个\r\n",
    "\r\n",
    "\r\n",
    "**示例 1：**\r\n",
    ">输入：`n = 2`\r\n",
    ">\r\n",
    ">输出：`2`\r\n",
    ">\r\n",
    ">解释：\r\n",
    "> 以下两个方案，都能实现 2 分钟内下载 2 个插件\r\n",
    ">- 方案一：第一分钟带宽加倍，带宽可每分钟下载 2 个插件；第二分钟下载 2 个插件\r\n",
    ">- 方案二：第一分钟下载 1 个插件，第二分钟下载 1 个插件\r\n",
    "\r\n",
    "**示例 2：**\r\n",
    ">输入：`n = 4`\r\n",
    ">\r\n",
    ">输出：`3`\r\n",
    ">\r\n",
    ">解释：\r\n",
    "> 最少需要 3 分钟可完成 4 个插件的下载，以下是其中一种方案:\r\n",
    "> 第一分钟带宽加倍，带宽可每分钟下载 2 个插件;\r\n",
    "> 第二分钟下载 2 个插件;\r\n",
    "> 第三分钟下载 2 个插件。\r\n",
    "\r\n",
    "\r\n",
    "\r\n",
    "**提示：**\r\n",
    "- `1 <= n <= 10^5`\r\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [Ju9Xwi](https://leetcode.cn/problems/Ju9Xwi/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [Ju9Xwi](https://leetcode.cn/problems/Ju9Xwi/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['2', '4']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastMinutes(self, n: int) -> int:\n",
    "        cur=1\n",
    "        res=0\n",
    "        while n>0:\n",
    "            if n<=cur:\n",
    "                n-=cur\n",
    "                \n",
    "            else:\n",
    "                cur*=2\n",
    "            res+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastMinutes(self, n: int) -> int:\n",
    "        \n",
    "        cur = 1\n",
    "\n",
    "        res = 0\n",
    "\n",
    "        while n > 0:\n",
    "            if n <= cur:\n",
    "                n -= cur\n",
    "                res += 1\n",
    "\n",
    "            else:\n",
    "                res += 1\n",
    "                cur *= 2\n",
    "            \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "\n",
    "class Solution:\n",
    "    def leastMinutes(self, n: int) -> int:\n",
    "        return math.ceil(math.log(n, 2)) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastMinutes(self, n: int) -> int:\n",
    "        return ceil(log(n,2))+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastMinutes(self, n: int) -> int:\n",
    "        m = 0\n",
    "        while n>1:\n",
    "            n /= 2\n",
    "            m += 1\n",
    "        return m+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def leastMinutes(self, n: int) -> int:\n",
    "        return math.ceil(log(n) / log(2)) + 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastMinutes(self, n: int) -> int:\n",
    "        ans = n\n",
    "        cnt = 1\n",
    "        while cnt < n:\n",
    "            ans = min(ans, (n + cnt - 1) // cnt + cnt.bit_length() - 1)\n",
    "            cnt <<= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastMinutes(self, n: int) -> int:\n",
    "        return math.ceil(math.log2(n))+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastMinutes(self, n: int) -> int:\n",
    "        if n <= 3:\n",
    "            return n\n",
    "        else:\n",
    "            return ceil(log(n,2))+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastMinutes(self, n: int) -> int:\n",
    "        temp, num_ops = 1, 0\n",
    "        while temp < n:\n",
    "            temp *= 2\n",
    "            num_ops += 1\n",
    "        return num_ops + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastMinutes(self, n: int) -> int:\n",
    "        i=1\n",
    "        j=0\n",
    "        while i<n:\n",
    "            i*=2\n",
    "            j+=1\n",
    "        return j+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastMinutes(self, n: int) -> int:\n",
    "        # if n == 1:\n",
    "        #     return 1\n",
    "        t = 1\n",
    "        dk = 1\n",
    "        while dk < n:\n",
    "            t += 1\n",
    "            dk *= 2\n",
    "        return t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastMinutes(self, n: int) -> int:\n",
    "\n",
    "        bandwidth = 1\n",
    "        count = 0\n",
    "\n",
    "        while bandwidth < n:\n",
    "            bandwidth *=2\n",
    "            count +=1\n",
    "\n",
    "        count +=1\n",
    "        return count\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "\n",
    "class Solution:\n",
    "    def leastMinutes(self, n: int) -> int:\n",
    "        return math.ceil(math.log(n,2))+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def leastMinutes(self, n: int) -> int:\n",
    "        init_speed = 1\n",
    "        time = 0\n",
    "        while True:\n",
    "            if n <= init_speed:\n",
    "                return time +1\n",
    "            else:\n",
    "                init_speed *= 2\n",
    "                time += 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastMinutes(self, n: int) -> int:\n",
    "        i=1\n",
    "        j=0\n",
    "        while i<n:\n",
    "            i*=2\n",
    "            j+=1\n",
    "        return j+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastMinutes(self, n: int) -> int:\n",
    "        ck=1\n",
    "        ans=1\n",
    "        while ck<n:\n",
    "            ans+=1\n",
    "            ck=ck*2\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastMinutes(self, n: int) -> int:\n",
    "        c = 1\n",
    "        i=1\n",
    "        while n > i:\n",
    "            c+=1\n",
    "            i*=2\n",
    "        return c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastMinutes(self, n: int) -> int:\n",
    "        import math\n",
    "        if n==1:\n",
    "            return 1\n",
    "        t = int(math.log(n, 2))\n",
    "        print(t)\n",
    "        return t+math.ceil(n/(2**t))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastMinutes(self, n: int) -> int:\n",
    "        ans = 0\n",
    "        speed = 1\n",
    "        while speed < n:\n",
    "            ans += 1\n",
    "            speed <<= 1\n",
    "        return ans + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastMinutes(self, n: int) -> int:\n",
    "        time = 0\n",
    "        bandwidth = 1\n",
    "        while True:\n",
    "            if bandwidth < n:\n",
    "                bandwidth *= 2\n",
    "                time += 1\n",
    "            else:\n",
    "                time += 1\n",
    "                break\n",
    "        return time\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def leastMinutes(self, n: int) -> int:\n",
    "        # > 输入：`n = 2`\n",
    "        # > 输出：`2`\n",
    "        # > 解释：\n",
    "        # > 以下两个方案，都能实现 2 分钟内下载 2 个插件\n",
    "        # > - 方案一：第一分钟带宽加倍，带宽可每分钟下载 2 个插件；第二分钟下载 2 个插件\n",
    "        # > - 方案二：第一分钟下载 1 个插件，第二分钟下载 1 个插件\n",
    "        # > 输入：`n = 4`\n",
    "        # > 输出：`3`\n",
    "        # > 解释：\n",
    "        # > 最少需要 3 分钟可完成 4 个插件的下载，以下是其中一种方案:\n",
    "        # > 第一分钟带宽加倍，带宽可每分钟下载 2 个插件;\n",
    "        # > 第二分钟下载 2 个插件;\n",
    "        # > 第三分钟下载 2 个插件。\n",
    "        times = 0\n",
    "        while (2 ** times) * 2 < n:\n",
    "            times += 1\n",
    "        speed = 2 ** times\n",
    "        return times + math.ceil(n / speed)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastMinutes(self, n: int) -> int:\n",
    "        l = int(log(n,2))\n",
    "        # print(l)\n",
    "        # print(2**l)\n",
    "        # print(n)\n",
    "        if 2**l>=n:\n",
    "            return l+1\n",
    "        else:\n",
    "            return l+2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastMinutes(self, n: int) -> int:\n",
    "        cnt = 0\n",
    "        l = 1\n",
    "        while l < n:\n",
    "            l *= 2\n",
    "            cnt += 1\n",
    "        return min([i - (-n) // 2 ** i for i in range(cnt+1)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastMinutes(self, n: int) -> int:\n",
    "        return ceil(log(n,2))+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastMinutes(self, n: int) -> int:\n",
    "        \n",
    "        cur = 1\n",
    "\n",
    "        res = 0\n",
    "\n",
    "        while n > 0:\n",
    "            if n <= cur:\n",
    "                n -= cur\n",
    "                res += 1\n",
    "\n",
    "            else:\n",
    "                res += 1\n",
    "                cur *= 2\n",
    "            \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastMinutes(self, n: int) -> int:\n",
    "        for i in range(n):\n",
    "            if 2 ** i >= n:\n",
    "                x = i+1\n",
    "                \n",
    "                break\n",
    "        if n > 2:\n",
    "            return x\n",
    "        else:\n",
    "            return n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastMinutes(self, n: int) -> int:\n",
    "        pre = inf \n",
    "        cur = n/(pow(2,0)) + 0\n",
    "        cnt = 1\n",
    "        while pre > cur :\n",
    "            pre = cur \n",
    "            cur = n/(pow(2,cnt)) + cnt\n",
    "            cnt += 1\n",
    "        return ceil(min(pre,cur))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastMinutes(self, n: int) -> int:\n",
    "        t = 0\n",
    "        dk = 1\n",
    "        while dk<n:\n",
    "            t += 1\n",
    "            dk *= 2\n",
    "        return t+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastMinutes(self, n: int) -> int:\n",
    "        #dp=[0,1]\n",
    "        speed=1\n",
    "        speed_time=1\n",
    "        #if n<=1:\n",
    "            #return dp[n]\n",
    "        if n==0:\n",
    "                return 0\n",
    "        elif n==1:\n",
    "                return 1\n",
    "        else:\n",
    "            while speed <n:#大于n时才会停止，所以speed_time里面多了1\n",
    "                speed*=2\n",
    "                speed_time+=1\n",
    "        return speed_time \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastMinutes(self, n: int) -> int:\n",
    "        v = 1\n",
    "        ans = 0\n",
    "        while n > v<<1:\n",
    "            ans += 1\n",
    "            v <<= 1\n",
    "        return ans + int(n>v) + 1\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastMinutes(self, n: int) -> int:\n",
    "        ans = 1\n",
    "        while(n!=1):\n",
    "            ans+=1\n",
    "            n = ceil(n/2)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastMinutes(self, n: int) -> int:\n",
    "        cur=1\n",
    "        res=0\n",
    "        while n>0:\n",
    "            if n<=cur:\n",
    "                n-=cur\n",
    "                res+=1\n",
    "            else:\n",
    "                res+=1\n",
    "                cur*=2\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def leastMinutes(self, n: int) -> int:\n",
    "        if n <= 3:\n",
    "            return n\n",
    "        n =  math.ceil(n / 2)\n",
    "        return int (self.leastMinutes(n) + 1 )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "\n",
    "class Solution:\n",
    "    def leastMinutes(self, n: int) -> int:\n",
    "\n",
    "        s=  math.log2(n)\n",
    "        if abs(s - int(s)) < 1e-8:\n",
    "            s = int(s)\n",
    "        else:\n",
    "            s = int(s)+1\n",
    "\n",
    "        return s+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastMinutes(self, n: int) -> int:\n",
    "        cur = 1\n",
    "        res = 0\n",
    "        while n > 0:\n",
    "            if n <= cur:\n",
    "                n -= cur\n",
    "                res += 1\n",
    "            else:\n",
    "                res += 1\n",
    "                cur *= 2\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef leastMinutes(self, n: int) -> int:\n",
    "\t\treturn math.ceil(log(n) / log(2)) + 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastMinutes(self, n: int) -> int:\n",
    "        l = int(log(n,2))\n",
    "        if 2**l>=n:\n",
    "            return l+1\n",
    "        else:\n",
    "            return l+2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef leastMinutes(self, n: int) -> int:\n",
    "\t\tif n < 3:\n",
    "\t\t\treturn n\n",
    "\t\telse:\n",
    "\t\t\treturn self.leastMinutes((n + 1) // 2) + 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastMinutes(self, n: int) -> int:\n",
    "        dp=[0,1]\n",
    "        speed=1\n",
    "        speed_time=1\n",
    "        if n<=1:\n",
    "            return dp[n]\n",
    "        else:\n",
    "            while speed <n:\n",
    "                speed*=2\n",
    "                speed_time+=1\n",
    "        return speed_time \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastMinutes(self, n: int) -> int:\n",
    "        cur = 1\n",
    "        res = 0\n",
    "        while n > 0:\n",
    "            if n <= cur:\n",
    "                n -= cur\n",
    "                res += 1\n",
    "\n",
    "            else:\n",
    "                res += 1\n",
    "                cur *= 2\n",
    "            \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastMinutes(self, n: int) -> int:\n",
    "        a=1\n",
    "        i=1\n",
    "        while a<n:\n",
    "            a=a*2\n",
    "            i=i+1\n",
    "        return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastMinutes(self, n: int) -> int:\n",
    "        d=1\n",
    "        index=1\n",
    "        while d<n:\n",
    "            index+=1\n",
    "            d=d*2\n",
    "        \n",
    "        return index"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastMinutes(self, n: int) -> int:\n",
    "        return math.ceil(log(n,2)+1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastMinutes(self, n: int) -> int:\n",
    "        if n==1:\n",
    "            return 1\n",
    "        else:\n",
    "            if n%2==0:\n",
    "                for i in range(1, n//2+1):\n",
    "                    if 2**i>=n:\n",
    "                        return i+1\n",
    "            else:\n",
    "                for i in range(1, (n+1)//2+1):\n",
    "                    if 2**i>=n:\n",
    "                        return i+1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef leastMinutes(self, n: int) -> int:\n",
    "\t\treturn math.ceil(log(n) / log(2)) + 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef leastMinutes(self, n: int) -> int:\n",
    "\t\treturn math.ceil(log(n) / log(2)) + 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastMinutes(self, n: int) -> int:\n",
    "\n",
    "        res = 1\n",
    "        nowspeed = 1\n",
    "        while n > 0:\n",
    "            if n>nowspeed:\n",
    "                res += 1\n",
    "                nowspeed *= 2\n",
    "            else:\n",
    "                return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastMinutes(self, n: int) -> int:\n",
    "        import math\n",
    "        m = 2\n",
    "        result = math.log(n, m)\n",
    "        if int(result)<result or int(result)>result:\n",
    "            result+=2\n",
    "        else :\n",
    "            result+=1\n",
    "        return int(result)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastMinutes(self, n: int) -> int:\n",
    "        ans = 0\n",
    "        while(n!=1):\n",
    "            ans+=1\n",
    "            n = ceil(n/2)\n",
    "        return ans+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastMinutes(self, n: int) -> int:\n",
    "        cur=1\n",
    "        time=0\n",
    "        while n>cur:\n",
    "            cur*=2\n",
    "            time+=1\n",
    "        time+=1\n",
    "        return time\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastMinutes(self, n: int) -> int:\n",
    "        if n==1:return 1\n",
    "        i=2\n",
    "        while not(2**(i-2) < n and n <= 2**(i-1)):\n",
    "            i+=1\n",
    "        return i\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastMinutes(self, n: int) -> int:\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        cur_bandwith = 1  # 初始带宽为1\n",
    "        min_minute = 1\n",
    "\n",
    "        while cur_bandwith < n:\n",
    "            min_minute += 1\n",
    "            cur_bandwith *= 2\n",
    "\n",
    "        return min_minute"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastMinutes(self, n: int) -> int:\n",
    "        return ceil(log(n, 2)) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastMinutes(self, n: int) -> int:\n",
    "        l = int(log(n,2))\n",
    "        # print(l)\n",
    "        # print(2**l)\n",
    "        # print(n)\n",
    "        if 2**l>=n:\n",
    "            return l+1\n",
    "        else:\n",
    "            return l+2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastMinutes(self, n: int) -> int:\n",
    "        def divide(a):\n",
    "            if a<2:\n",
    "                return 0\n",
    "            else:\n",
    "                return (divide(int(a/2)))+1\n",
    "\n",
    "        def change(p):\n",
    "            if float(int(p))<p:\n",
    "                return int(p)+1\n",
    "            else:\n",
    "                return int(p)\n",
    "            \n",
    "        return divide(n)+change(int(n)/int(pow(2,divide(n))))\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastMinutes(self, n: int) -> int:\n",
    "        c = 1\n",
    "\n",
    "        r = 0\n",
    "        while n>0:\n",
    "            if n<= c:\n",
    "                n -= c \n",
    "                r += 1\n",
    "            else:\n",
    "                r += 1\n",
    "                c *= 2\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "\n",
    "class Solution:\n",
    "    def leastMinutes(self, n: int) -> int:\n",
    "        dNum = 1\n",
    "        ans = 0\n",
    "        while True:\n",
    "            if n / dNum > (n / (dNum * 2)) + 1:\n",
    "                dNum *= 2\n",
    "                ans += 1\n",
    "            else:\n",
    "                return ans + math.ceil(n / dNum)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution(object):\n",
    "    def leastMinutes(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        result = math.ceil(log(n, 2)) + 1\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def leastMinutes(self, n: int) -> int:\n",
    "        return math.ceil(log(n,2))+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastMinutes(self, n: int) -> int:\n",
    "        i=0\n",
    "        speed=1\n",
    "        list1=[]\n",
    "        while speed<=n:\n",
    "            list1.append(ceil(n/speed)+i)\n",
    "            speed*=2\n",
    "            i+=1\n",
    "        return min(list1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastMinutes(self, n: int) -> int:\n",
    "        res = 1\n",
    "        spd = 1\n",
    "        while n/spd > 1:\n",
    "            spd *= 2\n",
    "            res += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastMinutes(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        n -= 1\n",
    "        ans = 0\n",
    "        while n > 0:\n",
    "            n >>= 1\n",
    "            ans += 1\n",
    "        return ans + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastMinutes(self, n: int) -> int:\n",
    "        \n",
    "        cur = 1\n",
    "\n",
    "        res = 0\n",
    "\n",
    "        while n > 0:\n",
    "            if n <= cur:\n",
    "                n -= cur\n",
    "                res += 1\n",
    "\n",
    "            else:\n",
    "                res += 1\n",
    "                cur *= 2\n",
    "            \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastMinutes(self, n: int) -> int:\n",
    "        return ceil(log(n,2))+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastMinutes(self, n: int) -> int:\n",
    "        cur = 1\n",
    "\n",
    "        res = 0\n",
    "\n",
    "        while n > 0:\n",
    "            if n <= cur:\n",
    "                n -= cur\n",
    "                res += 1\n",
    "\n",
    "            else:\n",
    "                res += 1\n",
    "                cur *= 2\n",
    "            \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastMinutes(self, n: int) -> int:\n",
    "        dp = [0] * (n + 1)  \n",
    "        dp[1] = 1\n",
    "        for i in range(2, n + 1):\n",
    "            dp[i] = dp[(i + 1) // 2] + 1\n",
    "        return dp[n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastMinutes(self, n: int) -> int:\n",
    "        dp=[1]*(n+1)\n",
    "        dp[1]=1\n",
    "\n",
    "\n",
    "        for i in range(2,n+1):\n",
    "            dp[i]=dp[(i+1)//2]+1\n",
    "        return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastMinutes(self, n: int) -> int:\n",
    "        dp=[0,1]\n",
    "        if n==1:return 1 \n",
    "        for i in range(2,n+1):\n",
    "            dp.append(dp[(i+1)//2]+1)        \n",
    "        return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def leastMinutes(self, n: int) -> int:\n",
    "        dp = [0] * (n+1)\n",
    "        dp[1] = 1\n",
    "        for i in range(2,n+1):\n",
    "            dp[i] = dp[int((i+1)/2)]+1\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastMinutes(self, n: int) -> int:\n",
    "        dp = [0] * (n+1)\n",
    "        dp[1] = 1\n",
    "        for i in range(2,n+1):\n",
    "            dp[i] = min(dp[i-1] + 1, dp[(i+1) // 2] + 1)\n",
    "\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastMinutes(self, n: int) -> int:\n",
    "        f = [0] * (n + 1)\n",
    "        f[1] = 1\n",
    "        for i in range(2, n + 1):\n",
    "            f[i] = f[(i + 1) // 2] + 1\n",
    "        return f[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastMinutes(self, n: int) -> int:\n",
    "        dp=[0]*(n+1)\n",
    "        dp[1]=1\n",
    "        for i in range(2,n+1):\n",
    "            dp[i]=dp[(i+1)//2]+1\n",
    "        return dp[n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def leastMinutes(self, n: int) -> int:\n",
    "        r=[ 0 for i in range(n+1)]\n",
    "        r[1]=1\n",
    "        j=1\n",
    "        if n>=2:\n",
    "            for i in range(2,n+1):\n",
    "                if   i == math.pow(2,j):\n",
    "                    r[i]=min(j+1,i)\n",
    "                    j=j+1\n",
    "                    u=r[i]+1\n",
    "                else:\n",
    "                    r[i]=min(u,i)\n",
    "        return r[n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastMinutes(self, n: int) -> int:\n",
    "        dp = [0] * (n+1)\n",
    "        dp[1] = 1 \n",
    "        for i in range(2,n+1):\n",
    "            dp[i] = 1 + min(dp[i-1],dp[(i+1)//2])\n",
    "        return dp[n]\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
